﻿#pragma once

#include<iostream>
#include<vector>
#include<time.h>
#include<assert.h>
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREE_LISTS = 208;

void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
	}
	void* Pop()
	{
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		return _freeList;
	}
	
	bool Empty()
	{
		return _freeList == nullptr;
	}
private:
	void* _freeList;
};

//计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 控制在12%左右的内碎片浪费
    // [1,128]              8byte对齐     freelist[0,16)
    // [129,1024]           16byte对齐    freelist[16,72)
    // [1025,8*1024]        128byte对齐   freelist[72,128)
    // [8*1024+1,64*1024]   1024byte对齐  freelist[128,184)

	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		return (((bytes)+align - 1) & ~(align - 1));
	}
	// 对齐大小计算，浪费大概在1%-12%左右
	static inline size_t RoundUp(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		if (bytes <= 128) {
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024) {
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8192) {
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 65536) {
			return _RoundUp(bytes, 1024);
		} 
		return -1;
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 映射的自由链表的位置
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {	
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8192) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 65536) {
			return _Index(bytes - 8192, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		return -1;
	}

};